\section{Kolorowanie krawędzi}
  Wprowadźmy pewne definicje analogiczne do używanych przy kolorowaniu wierzchołków.
  \begin{Def}
	\textit{Indeks chromatyczny} jest to minimalna liczba kolorów potrzebnych do poprawnego pokolorowania krawędzi grafu. Oznacza się go przez $\chi_e(G)$
  \end{Def}

  \begin{Def}
	Graf jest \textit{k-kolorowalny(e)}, jeśli istnieje dla niego poprawne kolorowanie krawędzi używające $k$ barw.
  \end{Def}

  Sąsiadujące krawędzie, to takie które mają po jednym z końców w tym samym wierzchołku. Tak więc, z żadnego wierzchołka nie może wychodzić kilka krawedzi jednakowej barwy. Łatwo zauważyć, że indeks chromatyczny grafu jest nie mniejszy niż największy stopień wierzchołka w tym grafie $\chi_e(G) \ge \Delta(G)$.

  \begin{Tw}[Vizing'a]
	Indeks chromatyczny grafu nie przekracza największego stopnia wierzchołka tego grafu o więcej niż 1. Czyli $\Delta(G) \ge \chi_e(G) \ge \Delta(G)+1$
  \end{Tw}
  Dowód twierdzenie można znaleźć w książce \cite{aspektykombinatoryki}.

  Tak więc, znając największy stopień wierzchołka mamy już bardzo ścisłe oszacowanie ilości kolorów potrzebnych do kolorowania krawędzi. Jednak już samo określenie, czy wystarczy $\Delta$ kolorów, czy jeden więcej, nie jest takie proste.

  Przypadkiem banalnym są cykle. Tutaj analogicznie do kolorowania wierzchołków, cykle o dlugości parzystej mają indeks chromatyczny $\chi_e(C_n)=2=\Delta(C_n)$, natomiast o długości nieparzystej $\chi_e(C_n)=3=\Delta(C_n)+1$.
  
  Określenie indeksu chromatycznego grafów pełnych także nie jest zbyt trudne.
  \begin{Tw}
	Graf pełny $K_n$ jest $n$-kolorowalny(e) dla $n$ nieparzystych lub $(n-1)$-kolorowalny(e) dla $n$ parzystych.
  \end{Tw}
  \begin{Dw}
	Rozważmy jako pierwsze grafy pełne $K_n$ o $n$ nieparzystym. Największa liczba krawędzi jednej barwy jest rowna $\frac{n-1}{2}$ a liczba krawędzi grafu pełnego to $|E|=\frac{n(n-1)}{2}$, gdyby graf ten był $(n-1)$-kolorowalny(e), to jego rozmiar wynosiłby co najwyżej $|E| \le \chi_e(K_n)\frac{(n-1)}{2}=\frac{(n-1)^2}{2}$, a zatem mamy sprzeczność. 

	Ustalmy jednak poprawne kolorowanie. Rozmieszczając wierzchołki po okręgu tak by tworzyły wielokąt foremny można zauważyć, że każda krawędź leżąca wewnątrz tego n-kąta jest równoległa do dokładnie jednej krawędzi będącej bokiem. Ponieważ krawędzie równoległe nie przecinają się w żadnym punkcie, można przy ich kolorowaniu użyć tej samej barwy. Tak więc, każdy z boków wielokąta otrzymuje różną barwę, a przekątne kolorujemy tak, jak bok równoległy, przez co otrzymujemy interesujące nas kolorowanie.

	\begin{figure}[!h]\centering\begin{tikzpicture}[scale=2]
	  \tikzstyle{every node}=[draw, circle, minimum size=5, inner sep=0]
	  \tikzstyle{c1}=[black]
	  \tikzstyle{c2}=[snake=zigzag, segment amplitude=1]
	  \tikzstyle{c3}=[densely dotted]
	  \tikzstyle{c4}=[dashed]
	  \tikzstyle{c5}=[snake=snake, segment amplitude=1, segment length=3]
	  \node(v1) at(0:1) {};
	  \node(v2) at(72:1) {}
		  edge[c1](v1);
	  \node(v3) at(144:1) {}
		  edge[c2](v2)
		  edge[c4](v1);
	  \node(v4) at(-144:1) {}
		  edge[c3](v3)
		  edge[c5](v2)
		  edge[c2](v1);
	  \node(v5) at(-72:1) {}
		  edge[c4](v4)
		  edge[c5](v1)
		  edge[c3](v2)
		  edge[c1](v3);
	\end{tikzpicture}\caption{}\end{figure}
	
	Dowód dla grafów $K_n$ o $n$ parzystym przeprowadzimy pokazując jak kolorować takie grafy. Wykorzystamy do tego kolorowanie grafu $K_{n-1}$ pokazane wyżej. Mając już pełny graf o $n-1$ wierzchołkach, pokolorowany powyższą metodą możemy zauważyć że 'naprzeciw' każdego boku leży wierzchołek nie będący incydentnym do żadnej krawędzi o barwie tego boku. Możemy zatem z każdego wierzchołka wyprowadzić po jednej dodatkowej krawędzi, nie zwiększając indeksu chromatycznego. Krawędzie te łączymy we wspólnym nowym wierzchołku przez co otrzymujemy pełny graf $K_n$ pokolorowany $n-1$ barwami.
  \end{Dw}

  Podobnie do przypadku grafów o nieparzystej liczbie wierzchołków, można rozważyć wszystkie spójne grafy regularne o nieparzystym rzędzie.
  \begin{Tw}
	Jeżeli $G=(V,E)$ jest grafem spójnym, w którym każdy wierzchołek jest stopnia $d$ oraz $|V|=n$, gdzie $n$ jest nieparzyste, to nie jest on $d$-kolorowalny(e).
  \end{Tw}
  \begin{Dw}
	Przy kolorowaniu krawędzi żaden kolor nie występuje wielokrotnie przy żadnym wierzchołku, więc liczba krawędzi o jednakowej barwie może wynosić najwyżej $\frac{n}{2}$. Ponieważ $n$ jest nieparzyste wynik całkowitego dzielenia nie zmieni się, gdy zredukujemy $n$ o $1$. Tak więc liczba krawędzi jednej barwy nie przekracza $\frac{n-1}{2}$. Liczba krawędzi w grafie regularnym wynosi $\frac{dn}{2}$. Liczba wszystkich krawędzi podzielona przez maksymalną liczbę krawędzi jednego koloru jest niemniejsza niż liczba kolorow użytych w kolorowaniu.
	\begin{center}
	 $\frac{\frac{1}{2}dn}{\frac{1}{2}(n-1)}=d\frac{n}{n-1} > d$
	\end{center}
	Widzimy zatem że $d$ jest mniejsze niż liczba kolorów potrzebnych do prawidłowego pokolorwania krawędzi grafu.
  \end{Dw}

  \begin{Tw}
	Grafy dwudzielne o maksymalnym stopniu wierzchołka $d$ mają indeks chromatyczny $\chi_e(G)=d$.
  \end{Tw}
  Dowód w książkach \cite{aspektykombinatoryki} oraz \cite{wprowadzeniedoteorii}.
  
  \newpage Jak było wspomniane na początku rozdziału, można przekształcić graf, w którym chcemy kolorować krawędzie tak, aby kolorować wierzchołki. Jest ono bardzo proste -- z każdej krawędzi tworzymy wierzchołek, a następnie łączymy go z tymi wierzchołkami, z którymi w pierwotnym grafie miał wspólny koniec. Graf uzyskany z takiego przekształcenia nazywamy \textit{grafem krawędziowym}. Przykład takiego przekształcenia przedstawia rysunek \ref{linegraph}: 
  \begin{figure}[!h]\centering\begin{tikzpicture}[scale=1.5]
	  \clip (-0.2,-0.5) rectangle (4.2,3.4);

	  \tikzstyle{Vnorm}=[inner sep=0, minimum size=6, draw=black,circle]
	  \tikzstyle{Enorm}=[thick]
	  \tikzstyle{Vdual}=[inner sep=0, minimum size=6, draw=gray!70, fill=lightgray!70,rectangle]
	  \tikzstyle{Edual}=[draw=gray, densely dashed]

	  \node(a)[Vnorm] at(0,0) {};
	  \node(b)[Vnorm] at(2,0) {}
		  edge[Enorm] (a);
	  \node(c)[Vnorm] at(3,1) {}
		  edge[Enorm] (b);
	  \node(d)[Vnorm] at(1,2) {}
		  edge[Enorm] (a)
		  edge[Enorm] (b);
	  \node(e)[Vnorm] at(4,2) {}
		  edge[Enorm] (c);
	  \node(f)[Vnorm] at(2,3) {}
		  edge[Enorm] (d)
		  edge[Enorm] (c)
		  edge[Enorm] (e);

	  \node(A)[Vdual] at(1,0) {};
	  \node(B)[Vdual] at(2.5, 0.5) {}
		  edge[Edual, bend left=65] (A);
	  \node(C)[Vdual] at(0.5, 1) {}
		  edge[Edual] (A);
	  \node(D)[Vdual] at(1.5,1) {}
		  edge[Edual] (A)
		  edge[Edual] (B)
		  edge[Edual] (C);
	  \node(F)[Vdual] at(3.5, 1.5) {}
		  edge[Edual, bend left] (B);
	  \node(G)[Vdual] at(2.5,2) {}
		  edge[Edual] (B)
		  edge[Edual] (F);
	  \node(H)[Vdual] at(1.5, 2.5) {}
		  edge[Edual, bend right=40] (C)
		  edge[Edual] (D)
		  edge[Edual] (G);
	  \node(I)[Vdual] at(3, 2.5) {}
		  edge[Edual, controls=(70:4.5) and (60:3), in=90] (H)
		  edge[Edual] (F)
		  edge[Edual] (G); 
  \end{tikzpicture}\caption{}\label{linegraph}\end{figure}

  Graf o wierzchołkach okrągłych to graf pierwotny (tj. ten który przekształcaliśmy) natomiast wierzchołki kwadratowe i krawędzie rysowane linią przerywaną przedstawiają graf po przekształceniu.\newline
